- realizarea de programe cu economie de resurse la dezvoltator datorita utilizarii de biblioteci
- realizarea de tranzactii rapide de catre utilizator.
Daca se cunosc structurile de date S1, S1, S2, S3, S4, ...... SN,
si trebuie rezolvata o problema P, cei care nu stiu proprietatile celor N structuri de date vor trece la elaborarea a N versiuni de program, fiecare versiune utilizand cate o structura de date dominanta.
Versiunile care se vor elabora sunt:
V1, V2, V3, V4, ...... VN.
Fiecare varianta are caracteristicile ei de performanta.
Se definesc cel putin 2 indicatori;
- gradul de ocupare a memoriei GUi cu i=1,2,3,....,N
- durata medie a tranzactiei pe baza caruia se calculeaza indicatorul de tranzactie ITi cu i=1,2,3,....,N .
GU i = LIUi / LTMi
ITi = TMEDi / max { TMEDi}
unde:
LIUi - lungimea zonei de memorie ocupata cu informatiua utila
LTM i - lungimea totala a zonei de memorie ocupata de structura de date
TMEDi - durata metie a tranzatiei pentru varianta Vi.
Indicele agregat de pergormanta pentru varianta V i, IAi este dat de relatia:
IAi = p1 * GUi + p2* ITi
unde p1 si p2 sunt coeficientii de importanta pentru alocarea de memorie si, respectiv, pentru viteza de executie a tranzactiilor.
Solicitand studentilor sa dea note de la zero la zece pentru cele doua criterii, s-au obtinut coeficientii de importanta:
| Seria | Numar studenti | p1 | p2 |
| C | Numar studenti | 0,45 | 0,55 |
| D | Numar studenti | 0,45 | 0,55 |
| E | Numar studenti | 0,42 | 0,58 |
| F | Numar studenti | 0,44 | 0,56 |
Daca se considera datele:
| Caracteristica | V 1 | V 2 | V 3 | V 4 |
| GU i | 0,40 | 0,30 | 0,80 | 0,50 |
| IT i | 0,60 | 0,70 | 0,50 | 0,70 |
| IAi = p1 * GUi + p2* ITi pentru: p 1 = 0,45 p 2 = 0,55 | 0,51 | 0,52 | 0,63 | 0,61 |
| In lista dubla sunt pentru fiecare element cate doua variabile pointer de lungime Lp si cate o zona de memorie pentru informatia utila de lungime LIU baiti. Lista dubla are x elemente. De asemenea, pentru referirea primului element din lista dubla este definita o variabila pointer de Lp baiti. Gradul de utilizare a memoriei GU pentru lista dubla este inferior celui pentru lista simpla, daca informatia utila are tot LIU baiti. |
| Modelul graf pentru un arbore oarecare conduce la evaluarea complexitatii folosind numarul ciclomatic, la un nivel egal cu 1. NN - numar de noduri NA - numar de arce. |
| Modelul graf pentru o lista simpla oarecare conduce la evaluarea complexitatii folosind numarul ciclomatic, la un nivel egal cu 1.
NN - numar de noduri NA - numar de arce. |
| Modelul graf pentru o lista dubla oarecare conduce la evaluarea complexitatii folosind numarul ciclomatic, la un nivel egal cu n.
NN - numar de noduri NA - numar de arce. |
| In cazul masivului unidimensional definit int a[n]; functiile suc() pentru referirea elementului succesor, adr() pentru furnizarea adresei unui element si pred() pentru referirea elementului precedent, evidentiaza faptul ca aceasta structura este omogena si se pot construi formule recursive pentru calculul de adresa si pentru referire. |
| In cazul listei duble, ,utilizarea functiei cont() si adr() evidentiaza modul in care se realizeaza legaturile dintre elemente. La creare trebuie sa se initializeze campul gama cu adresa elementului urmator si campul alfa cu adresa elementului precedent. |
Rezulta ca varianta V 3 este cea care utilizeaza structura de date adecvata.
Structurile de date statice sunt utilizate cand:
- se cunoaste suficient de riguros numarul de elemente ce formeaza colectivitatea care face obiectul prelucrarii cu ajutorul programului in care se utilizeaza structuri de date
- de la o rulare la alta numarul de elemente din structura care se initializeaza nu variaza semnificativ.
Pentru tot ce este legat de judete, se vor folosi variabile definite static.
Masivele unidimensionale vor avea 41 de componente.
Pentru tot ceea ce este legat de mediul rural si cel urban se vor folosi numai 2 componente.
Se defineste gradul de initializare GI astfel:
GI = NVI / NTV
unde:
NVI - numarul de elemente din structura initializate
NTV - numarul total de elemente care compun structura de date.
Daca un masiv unidimensional are 100 de componente, adica NTV = 100, din care 75 sunt initializate la o rulare, rezulta ca GI = 75 / 100 = 0,75.
Daca in ziua Z1 NVI1 = 60, in ziua Z2 NVI1 = 50, in ziua Z3 NVI1 = 40, in ziua Z4 NVI1 = 20, rezulta ca gradul mediu de initializare pentru K rulari, este dat de relatia:
GImed = (NVI1 + NVI2 + NVI3 + ..... + NVIK) / [K * max {NVI1, NVI2, NVI3,..., NVIK}]
Pentru datele obtinute corespunzator celor 4 rulari, rezulta:
GImed = (60 + 50 + 40 + 20) / (4 * 60) = 0,70
Structurile de date statice sunt utilizate cand:
- nu se cunoaste numarul de elemente care formeaza o colectivitate
- exista variatii foarte mari in numarul de componente din structura supuse initializarii de la o rulare a programului la alta.
Pentru elementele din colectivitate care corespund celor care vin sa cumpere un produs, datorita fluctuatiilor de la o zi la alta, se va lucra cu liste simple, ca structuri dinamice.
Pentru structurile dinamice, gradul de initializare GI = 1.
Zonele de memorie se caracterizeaza prin:
- lungime ca numar de baiti
- adresa de inceput
- continut ca sir de biti
- adresa de sfarsit, care se calculeaza functie de adresa de inceput si lungime
- tip care determina modul de interpretare a sirului de biti si stabileste operatiile ce se efectueaza.
Structurile de date sunt in final zone de memorie:
- contigue daca zonele sunt una langa cealalta
- dispersate, daca intre zonele de memorie ale unei structuri de date se afla fie zone nealocate, fie zone apartinand altor structuri de date.
Continutul unei zone de memorie se interpreteaza ca:
- numar intreg
- sir de caractere
- numar virgula mobila
- adresa de zona de memorie
- index
- deplasare
- cod de instructiune
- informatie de stare a executiei
- parola
- parametru
- contor.
Interpretarea este data de context. Acelasi continut poate avea mai multe semnificatii daca problema de rezolvat cere acest lucru.
Necesarul de memorie pentru a defini o structura de date include:
- zone de memorie pentru informatia utila, adica pentru informatia cu care se efectueaza calcule sau se fac alte prelucrari specifice lucrului cu siruri de caractere
- zone de memorie destinate regasirii de informatii sau pentru referirea de alte zone de memorie, adica variabile pointer.
programatorul are la dispozitie o multitudine de modalitati de a-si defini structurile de date.
Daca doreste existenta a numeroase facilitati, va defini multe variabile pointer.
Trebuie sa fie un echilibru intre volumul de operatii pe care il executa un program si necesarul de memorie.
Modelul grafic al structurii de date presupune detalierea la nivel de campuri a zonelor de memorie cu specificarea arcelor care definesc legaturile dintre elemente.
Modelul graf al structurii de date presupunelucru cu noduri si cu arce.
Modelul textual al structurii de date presupune descrierea structurii si proprietatilor acesteia folosind propozitii si fraze cat mai riguros construitre.
Modelul analitic al structurii de date presupune utilizarea de functii precum:
cont() pentru a obtine continutul zonei de memorie
adr() pentru a obtine adresa zonei de memorie
Lg() pentru a obtine lungimea zonei de memorie
suc() pentru a vedea care este elementul succesor
pred() pentru a vedea care este elementul predecesor.
Modelul bazat pe limbaj de programare al structurii de date presupune utilizarea instructiunilor necesare descrierii tipului, numelui si a modului in care este alcatuita structura.
Pentru structura de date masiv unidimensional definita prin:
tip nume[nr_componente];
reprezentarea cu ajutorul celor 4 modele impune utilizarea de reguli specifice.
Daca se foloseste limbajul de programare C++, pentru a defini un masiv unidimensional se va scrie una din instructiunile:
int a[100]; // masiv cu o suta de componente, de tin intreg
float b[44]; // masiv unidimensional de tip virgula mobila cu 44 de elemente
char zz[207]; // masiv unidimensional de tip caracter cu 207 componente
| In cazul modelului graf sunt necesare noduri si arce. Trebuie vazut cu exactitate ce arce leaga nodurile si cum sunt orientate arcele. |
| In cazul acestei zone de memorie, definita pe 2 baiti, avand numele alfa si adresa 0ABC0,iar continutul 01F5, prin aplicarea functiilor se va vedea exact care sunt elementele de definire ale acestei zone. Programatorul trebuie sa faca o definire exacta si completa a zonei de memorie. Absenta de informatii atrage dupa sine erori de programare. |
Rezulta ca:
- structurile de date contribuie la cresterea performantei programului
- reutilizarea de software este efectiva daca si numai daca bibliotecile construite pentru fiecare stuctura de date contin proceduri complet testate si daca in aceste biblioteci se regasesc implementate aceleasi operatii
- atunci cand se fac aprecieri asupra unei solutii trebuie sa se vina cu argumente solide, ceea ce inseamna ca trebuie sa existe indicatori acceptati si sa se compare valori obtinute cu acestia pentru toate variantele.
afisat azi 4 octombrie 2010
completat azi 11 octombrie 2010 ora 13,30